package com.hy;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Random;

/**
 * Created With IntelliJ IDEA.
 * Descriptions: 快排
 * author: Mr.Du
 * Date: 2022/11/7
 * Time: 21:44
 */
public class QuickSort {
    
    public static void main(String[] args) {
        QuickSort qSort = new QuickSort();
        int[] nums = new int[10];
        Random r = new Random();
        // 跑五次
        for(int i = 0;i < 5;i++){
            for(int j = 0; j < nums.length;j++){
                nums[j] = r.nextInt(1000);
            }
//            System.out.println("原数组: ");
//            System.out.println(Arrays.toString(nums));
//            qSort.quickSort(nums,0,nums.length-1);
//            System.out.println("堆排序后的数组: ");
//            System.out.println(Arrays.toString(nums));
            nums = new int[]{5,2,3,5,5,7,8};
            System.out.println("原数组: ");
            System.out.println(Arrays.toString(nums));
            qSort.threeWayQuickSort1(nums,0,nums.length-1);
            System.out.println("堆排序后的数组: ");
            System.out.println(Arrays.toString(nums));
        }
        
    }
    
    /**
     * 快排思想：(升序思想)
     *  找一个基准值，将小于基准值的放在左边，大于放在右边，一趟下来确定一个基准值位置
     *  将基准值左边和右边的继续上面操作
     * @param nums
     * @param start
     * @param end
     */
    public void quickSort(int[] nums, int start, int end){
        if(start < end){
            int left = start;
            int right = end;
            int tmp = nums[start];
            while(left < right){
                while(left < right && tmp <= nums[right]){
                    right--;
                }
                if(left < right){
                    nums[left] = nums[right];
                    left++;
                }
                while(left < right && tmp >= nums[left]){
                    left++;
                }
                if(left < right){
                    nums[right] = nums[left];
                    right--;
                }
            }
            nums[left] = tmp;
            quickSort(nums,start,left);
            quickSort(nums,left+1,end);
        }
    }

    /**
     * 使用三向切分快速排序对数组进行排序
     * 该方法递归地对数组的各个子区间进行三向切分快速排序
     *
     * @param arr 待排序的数组
     * @param low 子区间的起始索引
     * @param high 子区间的结束索引
     */
    public void threeWayQuickSort1(int[] arr, int low, int high) {
        // 当起始索引大于等于结束索引时，无需排序，直接返回
        if (low >= high) {
            return;
        }

        // 随机选择一个索引作为枢轴元素的索引
        int v = (int)(Math.random() * (high - low + 1) + low);
        // 将枢轴元素交换到区间起始位置
        swap(arr, low, v);
        // 获取枢轴元素的值
        int pivot = arr[low];
        // 初始化小于枢轴元素的边界
        int lt = low;
        // 初始化当前比较位置
        int i = low + 1;
        // 初始化大于枢轴元素的边界
        int gt = high;

        // 切分过程，根据枢轴元素将数组分为三部分
        while (i <= gt) {
            if (arr[i] < pivot) {
                // 当前元素小于枢轴元素，将其与小于边界后的元素交换，并移动小于边界和当前比较位置
                swap(arr, lt, i);
                lt++;
                i++;
            } else if (arr[i] > pivot) {
                // 当前元素大于枢轴元素，将其与大于边界前的元素交换，并移动大于边界
                swap(arr, i, gt);
                gt--;
            } else {
                // 当前元素等于枢轴元素，直接移动到下一个位置
                i++;
            }
        }
        // 递归地对小于枢轴元素的部分和大于枢轴元素的部分进行排序
        threeWayQuickSort1(arr, low, lt - 1);
        threeWayQuickSort1(arr, gt + 1, high);
    }


    /**
     * 三路快速排序
     * 三路快速排序是快速排序的一种优化，它将数组分为三个部分：
     * 小于基准值的元素、等于基准值的元素和大于基准值的元素。
     * 这样可以减少递归深度，提高排序效率。
     *
     * @param nums 待排序的数组
     * @param start 排序的起始位置
     * @param end 排序的结束位置
     */
    public void threeWayQuickSort(int[] nums, int start, int end) {
        // 当起始位置大于等于结束位置时，不需要排序
        if (start >= end) return;

        // 随机选择一个索引作为基准值的索引
        int v = (int)(Math.random() * (end - start + 1) + start);
        // 将基准值交换到数组的起始位置
        swap(nums, start, v);
        // 获取基准值
        int pivot = nums[start];
        // 初始化小于基准值的边界
        int lt = start;
        // 初始化当前比较位置
        int i = lt + 1;
        // 初始化大于基准值的边界
        int gt = end + 1;

        // 遍历数组，直到当前比较位置与大于基准值的边界相遇
        while (i < gt) {
            if (nums[i] < pivot) {
                // 当前元素小于基准值，将其与小于基准值边界的下一个位置交换
                swap(nums, i, lt + 1);
                // 更新当前比较位置和小于基准值的边界
                i++;
                lt++;
            } else if (nums[i] > pivot) {
                // 当前元素大于基准值，将其与大于基准值边界的前一个位置交换
                swap(nums, i, gt - 1);
                // 更新大于基准值的边界
                gt--;
            } else {
                // 当前元素等于基准值，继续比较下一个元素
                i++;
            }
        }
        // 将基准值交换到其最终位置（小于基准值边界的下一个位置）
        swap(nums, lt, start);
        // 递归地对小于基准值的部分进行排序
        threeWayQuickSort(nums, start, lt - 1);
        // 递归地对大于基准值的部分进行排序
        threeWayQuickSort(nums, gt, end);
    }

    public void quickSortInternal3(int[] arr, int l, int r) {
        if(l >= r) return;
        //随机取l-r之间的数
        int randIndex = (int)(Math.random() * (r - l + 1) + l);
        //主要还是以首元素作为基准值，只不过该基准值是每次随机取的，然后将随机所取的值与首元素交换
        //交换l与randIndex
        swap(arr,l,randIndex);
        //基准值为首元素
        int v = arr[l];
        //arr[l+1.....lt] < v
        //lt所处的位置就是arr[i]<v的最大边界
        int lt = l;
        //arr[gt....r] > v
        //gt所处的位置就是末尾元素
        int gt = r + 1;
        //i用来遍历数组，
        int i = l + 1;
        while(i<gt) {
            if(arr[i] < v) {
                //交换两者值,lt和i都自增1
                swap(arr,lt+1,i);
                lt++;
                i++;
            }else if(arr[i] > v) {
                //交换两者值,gt自减1
                swap(arr,gt-1,i);
                gt--;
            }else {
                //等于i自增
                i++;
            }
        }
        //交换l与lt元素,可以确定基准值的位置
        swap(arr,l,lt);
        //基准值前面继续进行上述操作
        quickSortInternal3(arr, l, lt-1);
        //基准值后面数组继续进行上述操作
        quickSortInternal3(arr, gt, r);
    }
    public void swap(int[] nums, int i, int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}
